1. Field Of The Invention
The present invention relates to optical character recognition systems and, more particularly, to methods and apparatuses for positioning a reference character template with respect to an unknown character pattern so as to be able to calculate a correlation factor between the two, and performing other character recognition processing related thereto.
2. Description Of The Related Art
In recent years, it has become possible to scan in paper copies of documents so as to form computerized images of such documents, analyze images in the text areas of the documents so as to recognize individual characters in the text data, and form computer readable files of character codes corresponding to the recognized characters. Such files can then be manipulated in word-processing, data-compression, or other information processing programs, and can also be used to retrieve the images of one or more of such documents in response to a query-based search of the text data. Such systems, which are hereinafter referred to as "character recognition systems", are advantageous because they eliminate the need to re-type or otherwise re-enter text data from the paper copies of the documents. For example, it is possible to recognition-process a document which has been transmitted by facsimile or reproduced from microfilm or by a photocopier so as to form computer text files that contain character codes (for example, ASCII character codes) of the characters in the document.
High accuracy optical character recognition systems employ a number of preliminary steps in order to isolate and pre-process individual character patterns within a bit map image of text, and then a correlation technique in order to determine the identity of each of the unknown character patterns. According to the correlation technique, plural reference character templates are selected sequentially from a library of such reference character templates, and a correlation factor is calculated between each such reference character template and the unknown character pattern. The correlation factor is a measure of similarity and varies between zero for no similarity to one for complete identity. Therefore, the identity of the unknown character pattern is designated according to the reference character template which yields the highest correlation factor to the unknown character pattern.
The process of computing a correlation factor between each reference character template and the unknown character pattern includes two steps. The first step involves positioning the reference character template with respect to the unknown character pattern, while the second step is the actual computation of the numerical value of the correlation factor, which as is well known can be calculated as follows: ##EQU1##
The first step, that is, the step of positioning the two images with respect to one another, is critically important because a small error in positioning can cause a large degradation in correlation. For example, an error of one pixel in vertical positioning has been known to Applicant to cause a reduction in the correlation factor of about 6%, i.e., a reduction in correlation from a perfect 1.000 to a correlation of 0.942. Because the reference character template which yields the highest correlation is designated as the identity of the unknown character pattern, it is readily apparent that an error in positioning can cause so great a reduction in the correlation factor that the unknown character pattern is identified incorrectly.
Various techniques for positioning the reference character template with respect to the unknown character pattern have been proposed, but all have drawbacks. For example, one known technique for positioning is to calculate, for each reference character template, the correlation factor at a variety of different relative positions and to select the highest correlation factor. Such a technique, while yielding accurate positioning data, is computationally too intensive to yield good OCR throughput. That is, because the above-noted correlation factor involves on the order of n.sup.2 calculations (where n is the height in pixels of a typical character and is ordinarily around 40) and because a typical library of reference character templates has about 100 entries, the number of calculations needed to obtain a correlation factor for each template is already very high. To add even a small 3.times.3 grid search for the highest correlation factor for each template multiplies that already high number by a factor of 9.
Another known technique for positioning involves centroid weighting in which the center of mass in the vertical and horizontal directions is computed both for the unknown character pattern and for each reference character template. The grids of the two images are then aligned so that their centers of mass coincide. Such a technique for positioning, while computationally efficient, is relatively inaccurate and fails completely when the unknown character pattern contains more than one character, such as when multiple characters are touching.
Other methods for positioning have been proposed, but each is different from the technique proposed herein, and each has disadvantages.